#include "Heapsort.h"

Heapsort::Heapsort()
{
    vetor = NULL;
    tamanho_vetor = 0;
    tamanho_elemento = 0;
    funcao_comparacao = NULL;
}

Heapsort::Heapsort(void* vetor, size_t tamanho_vetor, size_t tamanho_elemento, int(*comparador)(const void*,const void*))
{
    this->vetor = vetor;
    this->tamanho_vetor = tamanho_vetor;
    this->tamanho_elemento = tamanho_elemento;
    this->funcao_comparacao = comparador;
}

Heapsort::~Heapsort(){}

void* Heapsort::get(size_t posicao)
{
    if (posicao >= tamanho_vetor) return(NULL);
    return((byte*)vetor+tamanho_elemento*posicao);
}

void Heapsort::trocar(size_t primeiro, size_t segundo)
{
    if(primeiro == segundo) return;
    if(primeiro >= tamanho_vetor) return;
    if(segundo  >= tamanho_vetor) return;

    byte* a   = (byte*)get(primeiro);
    byte* b   = (byte*)get(segundo);
    byte* aux = new byte[tamanho_elemento];

    // Usar memcpy() equivale a usar:
    // for(size_t i=0 ; i<tamanho_elemento ; i++) aux[i] = a[i];

    // aux = a:
    memcpy(aux,a,tamanho_elemento);
    // a = b:
    memcpy(a,b,tamanho_elemento);
    // b = aux:
    memcpy(b,aux,tamanho_elemento);

    delete[] aux;
}

void Heapsort::max_heapify(size_t i, size_t tamanho_heap)
{
    size_t maior = i;
    size_t esq   = filho_esquerdo(i);
    size_t dir   = filho_direito(i);

    if(esq < tamanho_heap)
        if(funcao_comparacao(get(esq),get(maior)) > 0)
            maior = esq;

    if(dir < tamanho_heap)
        if(funcao_comparacao(get(dir),get(maior)) > 0)
            maior = dir;

    if(maior != i)
    {
        trocar(i,maior);
        max_heapify(maior,tamanho_heap);
    }
}

void Heapsort::build_max_heap()
{
    for(size_t i=(tamanho_vetor/2) ; i>0 ; i--)
        max_heapify(i,tamanho_vetor);
    max_heapify(0,tamanho_vetor);
}

void Heapsort::heapsort()
{
    if(this->vetor == NULL) return;

    // Contruir um heap usando os elementos do vetor:
    build_max_heap();

    // Setando o tamanho do heap:
    size_t tamanho_heap = tamanho_vetor;

    // Loop para remover o maior elemento do heap:
    while(tamanho_heap)
    {
        // Retirar o maior elemento do heap e passar para o final do vetor:
        trocar(0,(tamanho_heap-1));
        // Diminuindo o tamanho do heap:
        tamanho_heap--;
        // Consertando o heap:
        max_heapify(0,tamanho_heap);
    }
}

void Heapsort::heapsort(void* vetor, size_t tamanho_vetor, size_t tamanho_elemento, int(*comparador)(const void*,const void*))
{
    this->vetor = vetor;
    this->tamanho_vetor = tamanho_vetor;
    this->tamanho_elemento = tamanho_elemento;
    this->funcao_comparacao = comparador;
    this->heapsort();
}
